433. Minimum Genetic Mutation.go

package leetcode

// 解法一 BFS
funcminMutation(startstring, endstring, bank []string) int {
wordMap, que, depth:=getWordMap(bank, start), []string{start}, 0
forlen(que) >0 {
depth++
qlen:=len(que)
fori:=0; i<qlen; i++ {
word:=que[0]
que=que[1:]
candidates:=getCandidates433(word)
for_, candidate:=rangecandidates {
if_, ok:=wordMap[candidate]; ok {
ifcandidate==end {
returndepth
 }
delete(wordMap, candidate)
que=append(que, candidate)
 }
 }
 }
 }
return-1
}

funcgetWordMap(wordList []string, beginWordstring) map[string]int {
wordMap:=make(map[string]int)
fori, word:=rangewordList {
if_, ok:=wordMap[word]; !ok {
ifword!=beginWord {
wordMap[word] =i
 }
 }
 }
returnwordMap
}

funcgetCandidates433(wordstring) []string {
varres []string
fori:=0; i<26; i++ {
forj:=0; j<len(word); j++ {
ifword[j] !=byte(int('A')+i) {
res=append(res, word[:j]+string(rune(int('A')+i))+word[j+1:])
 }
 }
 }
returnres
}

// 解法二 DFS
funcminMutation1(startstring, endstring, bank []string) int {
endGene:=convert(end)
startGene:=convert(start)
m:=make(map[uint32]struct{})
for_, gene:=rangebank {
m[convert(gene)] =struct{}{}
 }
if_, ok:=m[endGene]; !ok {
return-1
 }
ifcheck(startGene^endGene) {
return1
 }
delete(m, startGene)
step:=make(map[uint32]int)
step[endGene] =0
returndfsMutation(startGene, m, step)
}

funcdfsMutation(startuint32, mmap[uint32]struct{}, stepmap[uint32]int) int {
ifv, ok:=step[start]; ok {
returnv
 }
c:=-1
step[start] =c
fork:=rangem {
ifcheck(k^start) {
next:=dfsMutation(k, m, step)
ifnext!=-1 {
ifc==-1||c>next {
c=next+1
 }
 }
 }
 }
step[start] =c
returnc
}

funccheck(valuint32) bool {
ifval==0 {
returnfalse
 }
ifval&(val-1) ==0 {
returntrue
 }
forval>0 {
ifval==3 {
returntrue
 }
ifval&3!=0 {
returnfalse
 }
val>>=2
 }
returnfalse
}

funcconvert(genestring) uint32 {
varvuint32
for_, c:=rangegene {
v<<=2
switchc {
case'C':
v|=1
case'G':
v|=2
case'T':
v|=3
 }
 }
returnv
}